package cn.aylog.simpleTree;

/**
 * 二叉树的增删改查操作
 */
public class BinaryTreeDemo2 {
    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();
        int[] arr = {39,8,7,6,5,4,3,2,1};
        // int[] arr = {6,7,8,9,10,11, 5,4,3};
        for (int v : arr) {
            tree.addNode(new Node(v));
        }
        // Node tar = tree.searchNode(6);
        // System.out.println(tar.getParentNode() + "-"+tar);
        // Node deleteNode = tree.deleteNode(6);
        // System.out.println(deleteNode);
        // tree.deleteNode(9);
        // tree.deleteNode(6);
        // tree.deleteNode(8);
        // tree.deleteNode(4);
        // tree.deleteNode(2);
        // tree.deleteNode(7);
        // tree.deleteNode(1);
        // tree.deleteNode(3);
        // tree.preOrder();
        tree.infixOrder();
        System.out.println("root " + tree.height());
        System.out.println("left " + tree.leftHeight());
        System.out.println("right " + tree.rightHeight());


    }

    static class BinaryTree {
        private Node root;

        public void addNode(Node node) {
            if (this.root == null) {
                this.root = node;
            } else {
                this.root.addNode(node);
            }
        }

        public void preOrder() {
            if (root == null) {
                System.out.println("树为空~~");
            } else {
                root.preOrder();
            }
        }


        public void infixOrder() {
            if (root == null) {
                System.out.println("树为空~~");
            } else {
                root.infixOrder();
            }
        }

        public Node searchNode(int value) {
            if (this.root != null) {
                return this.root.searchNode(value);
            } else {
                System.out.println("树为空~~");
                return null;
            }
        }

        public Node deleteNode(int value) {
            if (root != null) {
                if (root.value == value) {
                    Node ret = root;
                    // 由于根节点没有父节点所以需要额外处理
                    if (root.getLeftNode() == null && root.getRightNode() != null) {
                        root = root.getRightNode();
                        ret.setRightNode(null);
                    } else if (root.getLeftNode() != null && root.getRightNode() == null) {
                        root = root.getLeftNode();
                        ret.setLeftNode(null);
                    } else if (root.getLeftNode() == null && root.getRightNode() == null) {
                        root = null;
                    } else {
                        root.delete(value);
                    }
                    return ret;
                } else {

                    return root.delete(value);
                }
            } else {
                System.out.println("树为空~~");
                return null;
            }
        }

        public int rightHeight() {
            if (root == null) {
                return 0;
            }
            return root.rightHeight();
        }

        public int leftHeight() {
            if (root == null) {
                return 0;
            }
            return root.leftHeight();
        }

        public int height() {
            if (root == null) {
                return 0;
            }
            return root.height();
        }
    }

    private static Node parentNode = null; // 用于记录查找节点的父节点

    /**
     * 树节点类J
     */
    static class Node {
        private Integer value; // 值
        private Node leftNode; // 右子节点
        private Node rightNode; // 左子节点

        public Node(Integer value) {
            this.value = value;
        }

        public Integer getValue() {
            return value;
        }

        /**
         * 查找节点的父   0节点
         *
         * @return
         */
        public Node getParentNode() {
            return parentNode;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        public void preOrder() {
            System.out.println(this);
            if (this.getLeftNode() != null) this.getLeftNode().preOrder();
            if (this.getRightNode() != null) this.getRightNode().preOrder();
        }

        public void infixOrder() {
            if (this.getLeftNode() != null) this.getLeftNode().infixOrder();
            System.out.println(this);
            if (this.getRightNode() != null) this.getRightNode().infixOrder();
        }

        /**
         * 获取左子树的高度
         */
        public int leftHeight() {
            if (this.leftNode == null) {
                return 0;
            }
            return this.leftNode.height();
        }


        /**
         * 获取右子树的高度
         */
        public int rightHeight() {
            if (this.rightNode == null) {
                return 0;
            }
            return this.rightNode.height();
        }

        /**
         * 递归获取当前节点的树的高度
         *
         * @return 当前节点的高度
         */
        public int height() {
            return Math.max(this.leftNode == null ? 0 : this.leftNode.height(),
                    this.rightNode == null ? 0 : this.rightNode.height()) + 1;
        }

        /**
         * 节点新增
         *
         * @param node 待添加的节点
         */
        public void addNode(Node node) {
            if (this.value > node.getValue()) {
                if (this.leftNode == null) {
                    this.leftNode = node;
                } else {
                    this.leftNode.addNode(node);
                }
            } else {
                if (this.rightNode == null) {
                    this.rightNode = node;
                } else {
                    this.rightNode.addNode(node);
                }
            }
            // 检测是否需要进行左旋转
            if (rightHeight() - leftHeight() > 1) {
                leftRotate(this);
            }
            // 检测是否需要进行右旋转
            if(leftHeight() - rightHeight() > 1) {
                rightRotate(this);
            }

        }

        /**
         * 指定节点右旋转
         */
        private void rightRotate(Node node) {
            // 创建新节点，值与根节点一样
            Node newNode = new Node(node.value);
            Node temp = node.getLeftNode();
            // 设置新节点的左右节点
            newNode.setLeftNode(node.getLeftNode().getRightNode());
            newNode.setRightNode(node.getRightNode());
            // 重新设置根节点的相关数据
            node.value = node.getLeftNode().getValue();
            node.setRightNode(newNode);
            node.setLeftNode(node.getLeftNode().getLeftNode());
            // 将原来的根节点的第一个左节点的引用去掉，gc
            temp.setLeftNode(null);
            temp.setRightNode(null);
        }
        /**
         * 指定节点左旋转
         */
        private void leftRotate(Node node) {
            // 创建新节点，值与根节点一样
            Node newNode = new Node(node.value);
            Node temp = node.getRightNode();
            // 设置新节点的左右节点
            newNode.setLeftNode(node.getLeftNode());
            newNode.setRightNode(node.getRightNode().getLeftNode());
            // 重新设置根节点的相关数据
            node.value = node.getRightNode().getValue();
            node.setRightNode(temp.getRightNode());
            node.setLeftNode(newNode);
            // 将原来的根节点的第一个右节点的引用去掉，gc
            temp.setLeftNode(null);
            temp.setRightNode(null);
        }

        /**
         * 查找指定的节点
         *
         * @param value 值
         * @return 返回找到的节点否则返回null
         */
        public Node searchNode(int value) {
            if (this.value == value) {
                return this;
            }
            // 设置父节点
            parentNode = this;
            Node target = null;
            if (this.value > value && this.leftNode != null) {
                target = this.leftNode.searchNode(value);
            }
            if (target != null) {
                return target;
            }
            if (this.value <= value && this.rightNode != null) {
                target = this.rightNode.searchNode(value);
            }
            return target;
        }

        /**
         * 节点删除
         *
         * @param value 待删除的节点的值
         * @return 返回已经删除的节点
         */
        public Node delete(int value) {
            parentNode = null;
            Node target = this.searchNode(value);
            if (target == null) {
                return null;
            }
            Node parentNode = this.getParentNode();
            // 1.无左右子树, 叶子节点, 直接删除即可
            if (target.getLeftNode() == null && target.getRightNode() == null) {
                if (parentNode.getLeftNode() == target) {
                    parentNode.setLeftNode(null);
                } else {
                    parentNode.setRightNode(null);
                }
            } else if (target.getLeftNode() != null && target.getRightNode() == null) { // 2.1 只有左子树
                // 修改引用
                if (parentNode.getLeftNode() == target) {
                    parentNode.setLeftNode(target.getLeftNode());
                } else {
                    parentNode.setRightNode(target.getLeftNode());
                }
                target.setLeftNode(null); // 移除引用
            } else if (target.getRightNode() != null && target.getLeftNode() == null) { //2.2 只有右子树
                // 修改引用
                if (parentNode.getLeftNode() == target) {
                    parentNode.setLeftNode(target.getRightNode());
                } else {
                    parentNode.setRightNode(target.getRightNode());
                }
                target.setRightNode(null); // 移除引用
            } else {
                // 3.存在左子树和右子树
                // 从删除节点的右子树中查找做小值的节点或从左子树中查找最大值的节点
                // 从删除节点的右子树中查找最小值
                Node temp = target.getRightNode();
                while (temp.getLeftNode() != null) {
                    temp = temp.getLeftNode();
                }
                if (target.getRightNode() == temp) {
                    target.setRightNode(null);
                } else {
                    // 节点替换,需要先把找到的节点的引用给去掉,否则会死循环
                    this.searchNode(temp.value);
                    this.getParentNode().setLeftNode(null);
                }
                // 从删除节点的左子树中查找最大值
                // Node temp = target.getLeftNode();
                // while(temp.getRightNode() != null) {
                //     temp = temp.getRightNode();
                // }
                // if(target.leftNode == temp) {
                //     target.setLeftNode(null);
                // } else {
                //     // 节点替换,需要先把找到的节点的引用给去掉,否则会死循环
                //     this.searchNode(temp.value);
                //     this.getParentNode().setRightNode(null);
                // }
                target.replaceNode(temp);
            }

            return target;
        }

        /**
         * 节点数据替换
         *
         * @param node 新的节点的数据
         */
        private void replaceNode(Node node) {
            this.value = node.value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }
}

